package leetcode.editor.cn;

/**
 * @Author: Dempsey
 * @Data: 2021-01-07 22:30:54
 */

//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。 
//
// 进阶： 
//
// 
// 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4] 
//
// 示例 2： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1] 
//
// 示例 3： 
//
// 
//输入：nums = [], target = 0
//输出：[-1,-1] 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 105 
// -109 <= nums[i] <= 109 
// nums 是一个非递减数组 
// -109 <= target <= 109 
// 
// Related Topics 数组 二分查找 
// 👍 797 👎 0


public class P34 {
    public static void main(String[] args) {
        Solution solution = new P34().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int a = search(nums, target);
            int b = search(nums, target + 1);
            if (a == nums.length || nums[a] != target)
                return new int[]{-1, -1};
            return new int[]{a, b - 1};
        }

        int search(int[] nums, int t) {
            int l = 0, r = nums.length;
            while (l < r) {
                int m = (l + r) >>> 1;
                if (nums[m] < t)
                    l = m + 1;
                else
                    r = m;
            }
            return l;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}